/**
 * 221. Maximal Square 最大正方形
 * https://leetcode.com/problems/maximal-square/description/
 */
class MaximalSquare {
    public int maximalSquare(char[][] matrix) {
                if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return 0;
        }
        
        int m = matrix.length;
        int n = matrix[0].length;
        int maxSide = 0;
        
        // 使用一维数组优化空间复杂度
        int[] dp = new int[n + 1];
        int prev = 0; // 保存左上角的值
        
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                int temp = dp[j]; // 保存当前值，作为下一次的prev
                
                if (matrix[i-1][j-1] == '1') {
                    dp[j] = Math.min(Math.min(dp[j], dp[j-1]), prev) + 1;
                    maxSide = Math.max(maxSide, dp[j]);
                } else {
                    dp[j] = 0; // 当前格子为0，不能构成正方形
                }
                
                prev = temp; // 更新prev
            }
            prev = 0; // 每行开始时重置prev
        }
        
        return maxSide * maxSide; // 返回面积
    }
}